//给你一个链表数组，每个链表都已经按升序排列。
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//
//
// 示例 1：
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
//
//
// 示例 2：
//
// 输入：lists = []
//输出：[]
//
//
// 示例 3：
//
// 输入：lists = [[]]
//输出：[]
//
//
//
//
// 提示：
//
//
// k == lists.length
// 0 <= k <= 10^4
// 0 <= lists[i].length <= 500
// -10^4 <= lists[i][j] <= 10^4
// lists[i] 按 升序 排列
// lists[i].length 的总和不超过 10^4
//
//
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 2447 👎 0

import leetcodeauto.common.ListNode;


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/*
 推荐二分分治, 规模越大时, 合并次数越小, 规模越小时, 合并次数越多
 */
class Solution23
{
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return func(lists);
    }

    // 选出最小的头，剩下的继续递归去
    ListNode func(ListNode[] lists) {
        boolean allNull = true;
        int min = 0;
        int minVal = Integer.MAX_VALUE;
        // 选择链表头最小的链表
        for (int i = 0; i < lists.length; i++) {
            ListNode n = lists[i];
            if (n != null) { // 链表不等长，部分已经遍历完了
                if (n.val < minVal) {
                    min = i;
                    minVal = n.val;
                }
                allNull = false;
            }
        }

        if (allNull) {
            return null;
        }

        ListNode mergeHead = lists[min]; // 头最小的链表
        // 选个最小的, 剩下的递归去
        // for (int i = 0; i < lists.length; i++) {
        //     if (i == min) {
        //         lists[i] = lists[i].next;
        //     }
        // }
        lists[min] = lists[min].next;

        mergeHead.next = func(lists);

        return mergeHead;
    }
}

class Solution23_1 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        int N = lists.length - 1;
        return func(lists, 0, N);
    }

    ListNode func(ListNode[] lists, int L, int R) {
        if (L >= R) {
            return lists[L];
        }
        int mid = L + (R - L) / 2;
        ListNode left = func(lists, L, mid);
        ListNode right = func(lists, mid + 1, R);
        // 两个链表合并
        return mergeTwoLink(left, right);
    }

    private ListNode mergeTwoLink(ListNode left, ListNode right) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail = tail.next = left;
                left = left.next;
                // tail.next = null;
            } else {
                tail = tail.next = right;
                right = right.next;
                // tail.next = null;
            }
        }
        ListNode rest = left != null ? left : right;
        tail.next = rest;
        return dummy.next;
    }
}

//leetcode submit region end(Prohibit modification and deletion)

class Test23 {
    public static void main(String[] args) {
        ListNode[] lists = new ListNode[]{
                ListNode.from(new int[]{1, 4, 5}),
                ListNode.from(new int[]{1, 3, 4}),
                ListNode.from(new int[]{2, 6})
        };

        ListNode res = new Solution23_1().mergeKLists(lists);
        System.out.println(res.prettyString());
    }
}
